import sun.reflect.generics.tree.Tree;

import java.util.Stack;

public class Inorder {
    //二叉树中序非递归遍历
   public static void inorderTraversal(TreeNode root){
       Stack<TreeNode> stack =  new Stack<TreeNode>();
       TreeNode cur = root;
       //当根节点为空的时候就直接返回 不用遍历
       if (root == null){
           return;
       }
       while(cur != null || !stack.empty()){
           while(cur != null){
               stack.push(cur);
               cur = cur.left;
           }
           //此时沿着根节点向左的所有节点都已经入栈 也就是可以将栈顶元素打印了（也就是最左元素）
           cur = stack.pop();
           System.out.print(cur.val + " ");
           //打印完成后转向右子树
           cur = cur.right;
       }
   }

    public static void main(String[] args) {
        TreeNode root =  new TreeNode(1,null,null);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        inorderTraversal(root);
    }
}
